package leetcode;


public class SearchInsertPosition {

	public static void main(String[] args) {
		int[] array = {1, 3, 100,105,106};
//		searchInsert(array, 7);
		searchInsert(array, 0);
		searchInsert(array, 2);
		searchInsert(array, 3);
		searchInsert(array, 7);
		searchInsert(array, 15);
		searchInsert(array, 19);
	}
	public static int searchInsert(int[] A, int target) {
		if(A == null || A.length <= 0){
			return -1;
		}
        int index = realBinarySearch(A, target, 0, A.length - 1);
        System.out.println(index);
		return index;
	}
	public static int realBinarySearch(int[] array, int key ,int left, int right){
		if(left >= array.length){
			return left;
		}
		if(left > right){
			//一直纳闷为什么当初会返回left - 1，而且还可以AC，原来一直是true
			System.out.println(" is: " + (array[left] > key) );
			return array[left] > key ? left : left - 1;
		}
		int result = 0;
		int middle = left + (right - left) / 2;
		if(array[middle] == key){
			return middle;
		}
		if(array[middle] > key){
			result = realBinarySearch(array, key, left, middle - 1);
		}else {
			result = realBinarySearch(array, key, middle + 1, right);
		}
		return result;
	}
}
